# -*- coding: UTF-8 -*- #

import math
# 素数
# num = []
# def get_prime(n):
#     if n <= 1:
#         return "false"
#     for x in range(2, n+1):
#         print(x)
#         for y in range(2, x):
#
#             if(x % y == 0):
#                 # print("x="+str(x))
#                 break
#         else:
#             num.append(x)
#     return num
"""算法冒泡排序"""
# def func_bubble_sort():
#     s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
#     n = len(s)
#     for i in range(n):
#         for j in range(len(s)-1-i):
#             if s[j] > s[j+1]:
#                 s[j], s[j+1] = s[j+1], s[j]
#     print(s)


"""算法选择排序"""
# def func_select_sort():
#     s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
#     n = len(s)
#     for i in range(n):
#         index = i
#         for j in range(i + 1, len(s)):
#             if s[index] > s[j]:
#                 index = j
#             s[i], s[index] = s[index], s[i]
#     print(s)

""""算法直接插入排序"""
# def func_insert_sort():
#     arr = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
#     n = len(arr)
#     for i in range(1, n):
#         # 设置当前需要插入的元素
#         current = arr[i]
#         j = i - 1
#         while j >= 0 and arr[j] > current:
#             arr[j+1] = arr[j]
#             j -= 1
#         arr[j+1] = current
#
#     print(arr)

""""算法折半插入排序"""
def func_center_insert_sort():
    arr = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
    n = len(arr)
    for i in range(1, n):
        # 设置当前需要插入的元素
        current = arr[i]
        low = 0
        j = i - 1
        while low <= j:
            mid = math.floor((low + j)/2)
            if current > arr[mid]:
                low = mid + 1
                pass
            else:
                j = mid - 1
        for x in range(i, low, -1):
            arr[x] = arr[x-1]
            x -= 1
        arr[low] = current

    print(arr)

"""快速排序"""
def partition(arr, low, high):
    i = low-1 # 最小元素索引
    pivot = arr[high]
    for j in range(low , high):
        # 当前元素小于或等于 pivot
        if arr[j] <= pivot:
            i = i+1
            arr[i],arr[j] = arr[j],arr[i]
    arr[i+1],arr[high] = arr[high],arr[i+1]
    return i+1

# arr[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引
def func_quick_sort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        func_quick_sort(arr, low, pi-1)
        func_quick_sort(arr, pi+1, high)


"""并归排序"""
def merge_sort( list ):
    #不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素，不再拆分了
    if len(list) == 1:
        return list
    #取拆分的中间位置
    mid = math.floor(len(list) / 2)
    #拆分过后左右两侧子串
    left = list[:mid]
    right = list[mid:]
    left1 = merge_sort( left )
    right1 = merge_sort( right )

    return merge(left1 , right1)

#这里接收两个列表
def merge( left , right ):
    # 从两个有顺序的列表里边依次取数据比较后放入result
    # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
    result = []
    while len(left)>0 and len(right)>0 :
        #为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
        if left[0] <= right[0]:
            result.append( left.pop(0) )
        else:
            result.append( right.pop(0) )
    #while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
    result += left
    result += right
    return result

if __name__ == '__main__':
    list = [3,1,5,7,8,6,2,0,4,9]
    list = merge_sort(list)
    print(list)

    """n = len(list)
    func_quick_sort(list, 0, n-1)
    print(list)"""

    # func_center_insert_sort()
    """func_insert_sort()"""
    """func_bubble_sort()"""
    """func_select_sort()"""
    # num = get_prime(10)
    # print(num)
